#include <iostream>
#include <string>
using namespace std;

/**
 * min edit cost
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @param ic int整型 insert cost
 * @param dc int整型 delete cost
 * @param rc int整型 replace cost
 * @return int整型
 */
int dp[5005][5005] = {};
int minEditCost(string str1, string str2, int ic, int dc, int rc) {
    int m = str1.length(), n = str2.length();
    for(int i=0;i<=n;i++) dp[0][i] = i * ic;
    for(int i=0;i<=m;i++) dp[i][0] = i * dc;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(str1[i-1] == str2[j-1]) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = min(dp[i-1][j]+dc, min(dp[i-1][j-1]+rc, dp[i][j-1]+ic));
        }
    }
    return dp[m][n];
}


// 编辑距离2